package leetcode.editor.vscdev.hot100;
import leetcode.editor.utils.ListNode;

public class lc206 {
    public static void main(String[] args) {
        new Solution().reverseList(null);
        System.out.println("xx");
    }
}
class Solution {
    public ListNode reverseList(ListNode head) {
        // 采用递归实现
        // 当越过尾节点后终止递归，在回溯时修改各节点的 next 引用指向。
        return func(head, null);
    }
    // 递归实现
    private ListNode func(ListNode cur, ListNode pre){
        if(cur == null){
            return pre;
        }
        ListNode node = func(cur.next, cur);
        cur.next = pre;
        return node;
    }
    public ListNode reverseList1(ListNode head) {
        // 不采用新链表的情况完成该题
        // 双指针迭代
        ListNode pre = null, cur = head;
        // 就模拟头插一遍呗, 尾部是null, 最后cur遍历到null, pre是新头结点
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}
